//AVL tree (with left-right = 1 balance condition)


#include "stdio.h"
#include "stdlib.h"


typedef int elementType;

struct TreeNode
{
	elementType element;
	int height;
	struct TreeNode *left, *right;
};

typedef struct TreeNode *binarytree;
typedef struct TreeNode *position;


void makeEmpty(binarytree t);
position find(binarytree t, elementType x);
position findMin(binarytree t);
position findMax(binarytree t);
binarytree insertT(binarytree t, elementType x);
binarytree deleteT(binarytree t, elementType x);
elementType retrieve(binarytree t, position p); //position p->element retrieved from t



void makeEmpty(binarytree t)
{
	if(t){	
		makeEmpty(t->left);
		makeEmpty(t->right);
		free(t);
	}	
}

position find(binarytree t, elementType x)
{
	if(t == NULL)
		return NULL;
	
	if(x < t->element)
		return find(t->left, x);
	else if (x > t->element)
		return find(t->right, x);
	else
		return t;
}

position findMin(binarytree t)
{
	if(t != NULL)
		while(t->left != NULL)	
			t = t->left;
	
	return t;
}

position findMax(binarytree t)
{
	if(t != NULL)
		while(t->right != NULL)	
			t = t->right;
	
	return t;
}


int max(int h1, int h2){
	return ((h1>h2) ? h1:h2);
}

int height(binarytree t)
{
	if(t == NULL)
		return -1;
	else
		return t->height;
}

//left-left case
position SingleRotateWithLeft(position k2)
{
	//adjust pointers
	position k1 = k2->left;
	k2->left = k1->right;
	k1->right = k2;

	//adjust heights
	k2->height = max(height(k2->left), height(k2->right)) + 1;
	k1->height = max(height(k1->left), k2->height) + 1;

	return k1; //return new root
}

//right-right case
position SingleRotateWithRight(position k2)
{
	//adjust pointers
	position k1 = k2->right;
	k2->right = k1->left;
	k1->left = k2;

	//adjust heights
	k2->height = max(height(k2->left), height(k2->right)) + 1;
	k1->height = max(height(k1->right), k2->height) + 1;

	return k1; //return new root
}


//left-right case
position DoubleRotateWithLeft(position k3)
{
	position k1 = k3->left;
	position k2 = k1->right;

	//Double rotation is a sequence of single rotations with ht adjustments done in the single rotation function
	k3->left = SingleRotateWithRight(k1);
	return SingleRotateWithLeft(k3);
}


//right-left case
position DoubleRotateWithRight(position k3)
{
	position k1 = k3->right;
	position k2 = k1->left;

	//Double rotation is a sequence of single rotations with ht adjustments done in the single rotation function
	k3->right = SingleRotateWithLeft(k1);
	return SingleRotateWithRight(k3);
}

//Returns the new tree root, not inserted position
binarytree insertT(binarytree t, elementType x)
{
	if(t == NULL){
		t = (binarytree)malloc(sizeof(struct TreeNode));
		if(t){
			t->element = x;
			t->height = 0;  //empty tree has ht = -1
			t->left = t->right = NULL;			
		}
		else
			printf("Out of space");
		
	}
	else if(x < t->element){
		t->left = insertT(t->left, x);	//insert at left subtree potentially increasing its height
		if((height(t->left) - height(t->right)) == 2)  //ensure balancing done at closest possible unbalanaced node(from insertion point), left is bigger
			if(x < t->left->element) //left-left case (outer)
				t = SingleRotateWithLeft(t);
			else
				t = DoubleRotateWithLeft(t); //left-right case		
	}
	else if(x > t->element){
		t->right = insertT(t->right, x);			//insert at right subtree potentially increasing its height
		if((height(t->right) - height(t->left)) == 2)  //ensure balancing done at closest possible unbalanaced node(from insertion point)
			if(x > t->right->element) //right-right case (outer)
				t = SingleRotateWithRight(t);		//must set new value to t, else this function's copy not modified! >>>IMPORTANT
			else
				t = DoubleRotateWithRight(t); //right-left case		
	}
	
	//else x is in tree now(it was there already or was inserted)
	
	t->height = max(height(t->left), height(t->right)) + 1;
	return t; // return same tree as we got, x is in one of its subtrees(or was inserted there)
		
}

//complex, special cases when element found, for 2 children and 1 child. (for 2 children, t = min in right subtree)
//returns root of modified tree without x
binarytree deleteT(binarytree t, elementType x)
{
	binarytree tmp;
		
	if(t == NULL){
		printf("%d not found to delete\n", x);				
	}
	else if(x > t->element){
		t->right = deleteT(t->right, x);		 
	}
	else if(x < t->element){
		t->left = deleteT(t->left, x);		 
	}
	else if(t->left != NULL && t->right !=NULL){ // x is in tree t, start adjustments, 2 children, find smallest in right subtree
		tmp = findMin(t->right); //find min in right subtree
		t->element = tmp->element;	//copy its value
		t->right = deleteT(t->right, tmp->element); //delete the min from the right tree as its value is now copied to t, returns right subtree without x
	}
	else{	//0 or 1 child
		tmp = t;
		if(t->left == NULL)	//only right child or 0 children
			t = t->right;
		else if(t->right == NULL) //only left child
			t = t->left;
		free(tmp);
	}
			
	return t; // return same tree as we got, x is either deleted or was not found
	
	//after t is returned it will be connected up with its parent in the calling function

}

//Preorder : root first
void preorder(binarytree t, int level)
{
	int i;

	if(t){
		for(i=0; i<level; i++, printf(" "));
		printf("%d\n", t->element);
		preorder(t->left, level+1);		
		preorder(t->right, level+1);
	}
 }


int main(int argc, char* argv[])
{
	binarytree t=NULL;
	int i;

	for(i=0; i<5; i++){

		printf("Insert %d:\n", i);
		t = insertT(t, i);
		preorder(t, 0);
		printf("--------\n");
	}


	for(i=0; i<3; i++){
		printf("Delete %d:\n", i);
		t = deleteT(t, i);
		preorder(t, 0);
		printf("--------\n");
	}
	
			
	return 0;
}

